package leetcode.templates.manacher;
// 包含0点
public class Manacher01 {
	public String shortestPalindrome(String s) {
		if (s == null || s.length() == 0 || s.length() == 1)
			return s;
		char[] chars = s.toCharArray(); // 原串
		int len = chars.length;
		int sharpLen = (len << 1) - 1;// sharp串长度
		char[] sharp = sharp(chars, sharpLen);// sharp 串
		int[] radius = new int[sharpLen];// 回文半径数组
		int center = 0;// 遍历sharp串过程中的最右回文中心
		int range = 0;// 遍历sharp串过程中的最右回文中心与该点回文半径覆盖到的最远不可达坐标
		int max = 0;// 最长回文半径
		int maxCenter = 0;// sharp串的最大回文串中心
		int ansCenter = 0;// 原char[]中, 以0坐标字符(第一个字符)为回文一部分的最大回文子串的中心点
		int ansRadius = 0;// ansCenter的回文半径
		for (int i = 0; i < sharpLen; i++) {
			radius[i] = range > i ? Math.min(range - i, radius[(center << 1) - i]) : 1;
			while (i - radius[i] >= 0 && i + radius[i] < sharpLen) {
				if (sharp[i - radius[i]] == sharp[i + radius[i]]) {
					radius[i]++;
				} else {
					break;
				}
			}
			if (i + radius[i] > range) {
				center = i;
				range = i + radius[i];
			}
			if (radius[i] > max) {
				max = radius[i];
				maxCenter = i;
				if (max == maxCenter + 1) {
					ansCenter = maxCenter >> 1;
					ansRadius = radius[i] >> 1;
				}
			}
		}
		// [a, #, a, #, c, #, e, #, c, #, a, #, a, #, a]
		// 原数组以0坐标为回文串一部分的最大回文右边界
		int right = ansRadius + ansCenter;
		// 需要添加的字符个数
		int addLen = len - 1 - right;
		// 最短回文串数组
		char[] ans = new char[len + addLen];
		// 尾部倒叙添加到结果头部,形成回文串
		int p = len - 1;
		int i = 0;
		for (; i < addLen; i++) {
			ans[i] = chars[p--];
		}
		// 原串接续到结果尾部
		p = 0;
		for (; i < ans.length; i++) {
			ans[i] = chars[p++];
		}
		return new String(ans);
	}

	// 原串中间添加#
	private char[] sharp(char[] chars, int len) {
		char[] ans = new char[len];
		int p = 0;
		for (int i = 0; i < len; i++) {
			if ((i & 1) == 0) {
				ans[i] = chars[p++];
			} else {
				ans[i] = '#';
			}
		}
		return ans;
	}

//作者：wa-pian-d
//链接：https://leetcode.cn/problems/shortest-palindrome/solution/wa-pian-214-zui-duan-hui-wen-chuan-java-x506l/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
